package com.lw.leetcode.binary.b;

/**
 * binary
 * 1292. 元素和小于等于阈值的正方形的最大边长
 *
 * @Author liw
 * @Date 2021/6/12 16:09
 * @Version 1.0
 */
public class MaxSideLength {

    public static void main(String[] args) {
        MaxSideLength test = new MaxSideLength();
//        int[][] arr = {{1,1,3,2,4,3,2},{1,1,3,2,4,3,2},{1,1,3,2,4,3,2}};

        // mat = [[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]], threshold = 1
//        int[][] arr = {{2,2,2,2,2},{2,2,2,2,2},{2,2,2,2,2},{2,2,2,2,2},{2,2,2,2,2}};

        // mat = [[1,1,1,1],[1,0,0,0],[1,0,0,0],[1,0,0,0]], threshold = 6
//        int[][] arr = {{1,1,1,1},{1,0,0,0},{1,0,0,0},{1,0,0,0}};

        // mat = [[18,70],[61,1],[25,85],[14,40],[11,96],[97,96],[63,45]], threshold = 40184
        int[][] arr = {{18, 70}, {61, 1}, {25, 85}, {14, 40}, {11, 96}, {97, 96}, {63, 45}};
        int i = test.maxSideLength(arr, 40184);
        System.out.println(i);
    }

    public int maxSideLength(int[][] mat, int threshold) {
        int a = mat.length;
        int b = mat[0].length;
        int[][] arr = new int[a + 1][b + 1];
        int min = 0;
        for (int i = 1; i <= a; i++) {
            for (int j = 1; j <= b; j++) {
                arr[i][j] = mat[i - 1][j - 1] + arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1];
                int st = 0;
                int end = Math.min(i, j);
                while (st <= end) {
                    int m = st + ((end - st) >> 1);
                    int sum = arr[i][j] + arr[i - m][j - m] - arr[i - m][j] - arr[i][j - m];
                    if (sum <= threshold) {
                        st = m + 1;
                        min = Math.max(m, min);
                    } else {
                        end = m - 1;
                    }
                }
            }
        }
        return min;
    }

}
